package algorithm_primary.studyMySelf.四十二ReceivingRainwater;

/**
 * @author 衡孟浩
 * @date 2023/8/14 10:21
 * <p>
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * 示例 2：
 * <p>
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 * <p>
 * <p>
 * 提示：
 * <p>
 * n == height.length
 * 1 <= n <= 2 * 104
 * 0 <= height[i] <= 105
 */
public class TestMain {

    public static void main(String[] args) {
        int[] height = {5,0,1,0,1,0,1,0,1};
        int trap = trap(height);
        System.out.println("trap = " + trap);
    }


    /**
     * 原始解法
     * @param height
     * @return
     */
//    public static int trap(int[] height) {
//        int sum = 0;
//        for (int i = 1; i < height.length - 1; i++) {
//            // i 表示当前列 因为第一列和倒数第一列肯定是不能存水的所以   我们计算的时候从第一列和倒数第二列开始
//            // 当前列 找到右边最大列  左边最大列leftMax  并且求出来两边最大列中的最小值rightMax minForMax
//            // 如果当前列的值小于  minForMax  那么说明 当前列比左右两边都小  所以肯定是能存水的
//            // 但是能存多少水 取决于当前的minForMax多高   可以想象一下
//            //  当前列左边有高的   右边有高的   那么他能存多少水取决于当前列和左右中低的差值
//            // 如果minForMax小于或者等于当前列，那么当前列肯定不会存水
//
//
//            // 寻找最左边
//            int leftMax = getMaxLeft(i, height);
//            int rightMax = getMaxRight(i, height);
//
//            int minForMax = Math.min(leftMax, rightMax);
//
//            if (minForMax > height[i]) {
//                sum = sum + (minForMax - height[i]);
//            }
//        }
//        return sum;
//    }


    // 动态规划
    /*public static int trap(int[] height) {
        int sum = 0;
        int leftMax = getMaxLeft(0,height);
        int[] rightMaxList = getMaxRightList(height);
        for (int i = 1; i < height.length - 1; i++) {
            // i 表示当前列 因为第一列和倒数第一列肯定是不能存水的所以   我们计算的时候从第一列和倒数第二列开始
            // 当前列 找到右边最大列  左边最大列leftMax  并且求出来两边最大列中的最小值rightMax minForMax
            // 如果当前列的值小于  minForMax  那么说明 当前列比左右两边都小  所以肯定是能存水的
            // 但是能存多少水 取决于当前的minForMax多高   可以想象一下
            //  当前列左边有高的   右边有高的   那么他能存多少水取决于当前列和左右中低的差值
            // 如果minForMax小于或者等于当前列，那么当前列肯定不会存水


            // 寻找最左边
            leftMax = Math.max(leftMax, height[i]);
            int rightMax = rightMaxList[i];

            int minForMax = Math.min(leftMax, rightMax);

            if (minForMax > height[i]) {
                sum = sum + (minForMax - height[i]);
            }
        }
        return sum;
    }*/

//    public int trap(int[] height) {
//          int sum = 0;
//          int leftIndex = 1,rightIndex = height.length -2;
//          int leftMaxLine = height[0],rightMaxLine = height[height.length-1];
//          while (leftIndex < rightIndex){
//              leftMaxLine = Math.max(leftMaxLine,height[leftIndex]);
//              rightMaxLine = Math.max(rightMaxLine,height[rightIndex]);
//              if (leftMaxLine <= rightMaxLine){
//                  sum = sum + (height[leftIndex] - leftMaxLine);
//                  leftIndex ++;
//              } else {
//                  sum = sum + (height[leftIndex] - leftMaxLine);
//                  leftIndex ++;
//              }
//          }
//    }
    public static int trap(int[] height) {
        int ans = 0;
        int n = height.length;
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;

        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);

            if (height[left] <= height[right]) {
                ans += leftMax - height[left];
                left++;
            } else {
                ans += rightMax - height[right];
                right--;
            }
        }

        return ans;
    }


    private static int[] getMaxRightList(int[] height) {
        int[] re = new int[height.length];
        int max = height[height.length -1];
        for (int i = height.length -2; i >= 1; i--) {
            max = Math.max(max,height[i]);
            re[i] = max;
        }
        return re;
    }

    private static int getMaxRight(int i, int[] height) {
        int rightMax = height[i];
        for (int i1 = i; i1 < height.length; i1++) {
            if (height[i1] > rightMax) {
                rightMax = height[i1];
            }
        }
        return rightMax;
    }

    private static int getMaxLeft(int i, int[] height) {
        int leftMax = height[i];
        for (int i1 = i; i1 >= 0; i1--) {
            if (height[i1] > leftMax) {
                leftMax = height[i1];
            }
        }
        return leftMax;
    }



}
